#-*- coding: utf-8 -*-
"""
Exemple de solution de la question 2 du test.
Pour chaque contrainte à TRUE, elle est vérifiée.
Si i est avant j (pas vérifiée), j est insérée juste avant i.
Pour savoir si les contraintes sont incompatibles, il suffit 
d'avoir effectué des changements en partant du dernier résultat.

Une autre approche (proposée par Jason) est cependant bien plus simple :
*	Stocker une liste avec les tâches à ordonnancer et les tâches exécutées
*	Tant qu'il reste des tâches à ordonnancer,
* 		Y a-t-il une tâche sans aucune contrainte ?
*			Vrai ?	On élimine cette tâche des tâches à ordonnancer 
*					et on l'ajoute aux tâches exécutées.
*			Faux ?	On arrête, les contraintes sont incompatibles !
* 	Retourner la liste des tâches exécutées.
"""

def dbg(mat):
	"""Affiche ligne par ligne le contenu d'une matrice de contraintes."""
	for ligne in mat:
		print ligne

def creer_matrice(n_taches, contraintes):
	"""Crée une matrice de booléens contenant les contraintes sur chaque tâche."""
	mat = [[False] * n_taches for x in range(n_taches)]
	for i, j in contraintes:
		mat[i][j] = True
	return mat

def ordonnanceur(mat):
	"""Ordonnanceur de tâches (version de base, réponse acceptée au test !)"""
	tasks = range(len(mat))
	for i in range(len(mat)):
		for j in range(len(mat)):
			#pour chaque élément...
			#est-ce que la contrainte est vérifiée ?
			#si c'est le cas : rien à faire
			#sinon, faut changer l'ordre
			if mat[i][j] == True:
				"""
				print "analyse de la condition", i, j
				print "situation :", tasks
				"""
				#regardons si j est avant i
				indiceI = -1
				indiceJ = -1
				for pos, t in enumerate(tasks):
					#on stocke les indices si nécessaire
					if t==j:
						indiceJ = pos
						"""print '>>> trouvé j !'"""
					elif t==i:
						indiceI = pos
						"""print '>>> trouvé i !'"""
					#est-ce qu'on a trouvé un des deux ?
					if indiceI == -1:
						if indiceJ != -1:
							"""print '>>> RIEN À FAIRE'"""
							#rien à faire : j avant i
							break
					elif indiceJ != -1:
						#faut insérer avant
						"""print '>>> INSÉRER AVANT'"""
						tasks.insert(indiceI, tasks.pop(indiceJ))
						break
	return tasks

def ordonnanceur_better(mat, tasks_list=None):
	"""
	Ordonnanceur amélioré : une matrice de contraintes doit être donnée.
	Si une liste de tâches est donnée,
		* Cette liste est utilisée dès le départ.
		* La fonction renvoit un indicateur de changement.
		(si cet indicateur est à True, il n'y a pas* de solution !)
	Sinon, l'appel à range est fait en interne et le résultat est renvoyé.
	
	(*) En effet, la fonction n'est pas supposée se tromper lorsque 
	les contraintes ne sont pas incompatibles. Si elle a encore quelque chose 
	à modifier après un premier appel, c'est qu'il n'y a pas de solution.
	"""
	if isinstance(tasks_list, list):
		#ordre de départ déjà donné en paramètre
		#pas de deepcopy, il sera directement modifié.
		tasks = tasks_list
	else:
		#par défaut, ordre croissant...
		tasks = range(len(mat))
	changed = False #init de l'indicateur
	for i in range(len(mat)):
		for j in range(len(mat)):
			if mat[i][j] == True:
				#est-ce que la contrainte est vérifiée ?
				#regardons si j est avant i
				#si c'est le cas : rien à faire
				#sinon, faut changer l'ordre
				indiceI = -1 #pas trouvée
				indiceJ = -1 #pas trouvée
				for pos, t in enumerate(tasks):
					#on stocke les indices si on est dessus
					if t==j:
						indiceJ = pos
					elif t==i:
						indiceI = pos
					#est-ce qu'on a trouvé un des deux à ce moment-ci ?
					if indiceI == -1:
						if indiceJ != -1:
							#rien à faire : j est déjà avant i
							break
					elif indiceJ != -1:
						#il faut insérer j avant i
						changed = True #indicateur p-ê retourné plus tard...
						tasks.insert(indiceI, tasks.pop(indiceJ)) #aucun décalage nécessaire
						break
	if isinstance(tasks_list, list):
		#on retourne un indicateur (rappel : la liste de tâches est directement modifiée.)
		return changed
	else:
		#on retourne la liste de tâches (sinon, on perd le résultat...)
		return tasks

def ordonnanceur_test(lbl, n_tasks, cstr):
	u"""
	Les tests de cette fonction vérifient que creer_matrice et ordonnanceur_better fonctionnent.
	Ce ne serait pas tout à fait la même chose si on utilisait ordonnanceur :
	cette dernière est incapable de voir si les conditions sont incompatibles.
	Ç'aurait peut-être été plus propre de tester chaque fonction séparément...
	
	>>> ordonnanceur_test(u"Énoncé de l'examen", 4, [(2, 0), (2, 1), (0, 1), (3, 2)])
	Énoncé de l'examen
	[False, True, False, False]
	[False, False, False, False]
	[True, True, False, False]
	[False, False, True, False]
	Solution trouvée : [1, 0, 2, 3]
	>>> ordonnanceur_test(u"Perso (et impossible)", 2, [(0,1),(1,0)])
	Perso (et impossible)
	[False, True]
	[True, False]
	Impossible !
	"""
	print lbl
	mat = creer_matrice(n_tasks, cstr)
	dbg(mat)
	sol = ordonnanceur_better(mat)
	if ordonnanceur_better(mat, sol):
		print u"Impossible !"
	else:
		print u"Solution trouvée :", sol


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=True)